5337. Different-different

Given n integers. Find out how many of them are different.

Input. The first line contains the number of integers n (1 ≤ n ≤ 10⁶). The second line contains n integers, each of which does not exceed 2 * 10⁹ in absolute value.

Output. Print the number of different integers among the given ones.

Sample input	Sample output
5 9 15 22 15 22	3

SOLUTION

data structures - set

Algorithm analysis

Solution using the set data structure. Put all elements into a set. Each number will be added to the set only once. Then print the size of the set. The complexity is O(n log₂n).

Solution using sorting. Place the numbers into an array and sort it. Identical numbers will be placed next to each other. Iterate through the array, counting the number of different neighboring elements. Adding one to this count will give the number of different elements in the array. The complexity is O(n log₂n).

Algorithm realization

Declare the set s.

set<int> s;

Read the input data. Add all numbers to the set.

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&val);

s.insert(val);

}

Print the size of set s, the number of distinct integers among the given ones.

printf("%d\n",s.size());

Algorithm realization – sorting

Read the input data. Store the input numbers into an array.

scanf("%d", &n);

v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Sort an array.

sort(v.begin(), v.end());

Count the number of different neighboring elements in the array using the variable cnt. Initially, set cnt to 1.

cnt = 1;

for (i = 0; i < n - 1; i++)

if (v[i] != v[i + 1]) cnt++;

Print the answer.

printf("%d\n", cnt);

Algorithm realization – sorting + unique

Read the input data. Store the input numbers into an array.

scanf("%d", &n);

v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Sort an array.

sort(v.begin(), v.end());

Compute and print the number of distinct elements in the array.

res = unique(v.begin(), v.end()) - v.begin();

printf("%d\n", res);

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

TreeSet<Integer> s = new TreeSet<Integer>();

int n = con.nextInt();

for(int i = 0; i < n; i++)

{

int val = con.nextInt();

s.add(val);

}

System.out.println(s.size());

con.close();

}

}

Java realization – sort

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

for(int i = 0; i < n; i++)

m[i] = con.nextInt();

Arrays.sort(m);

int cnt = 1;

for (int i = 0; i < n - 1; i++)

if (m[i] != m[i + 1]) cnt++;

System.out.println(cnt);

con.close();

}

}

Python realization

Read the input data.

n = int(input())

lst = list(map(int,input().split()))

Convert the list lst into a set which automatically removes any duplicate elements. Then compute and print the number of elements in this set.

print(len(set(lst)))